//==============================================================================
//
//   DSortedList - the sorted double linked list class in the ofc-library
//
//               Copyright (C) 2004  Dick van Oudheusden
//  
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public
// License as published by the Free Software Foundation; either
// version 2 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public
// License along with this library; if not, write to the Free
// Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
//
//==============================================================================
// 
//  $Date: 2004-07-25 09:11:53 $ $Revision: 1.4 $
//
//==============================================================================

#include "ofc/DSortedList.h"

#include "ofc/DText.h"

#include "ofc/DComparable.h"

#if _INTERFACE_

#include "ofc/config.h"

#include "ofc/DList.h"

//
// The DSortedList class implements a number of methods for using a sorted double linked
// lists. This class maintains a sorted list. During inserting of objects this list is
// kept sorted. As a result a number of insert related methods of the parent @class(DList)
// are disabled and return a warning.
// 
 
@interface DSortedList : DList
{
@private
  BOOL            _ascending; // is the list sorted ascending ? (else descending)
  Class           _class;     // the class of the objects
}

#endif



@implementation DSortedList


//// Constructors

//
// Initialise an empty ascending sorted list
//
// @return the list
//

- (DSortedList *) init
{
  [super init];

  _class     = Nil;
  _ascending = YES;
  
  return self;
}

//
// Initialise a sorted list
// 
// @param class        the class of the objects (conforms to comparable protocol)
// @param ascending    should the list be sorted ascending ?
// 
// @return the list
// 

- (DSortedList *) init :(Class) class :(BOOL) ascending
{
  [self init];

  [self class     :class];
  [self ascending :ascending];
    
  return self;
}

//// Deconstructor

//
// Free the list (the stored objects are *NOT* freed)
//
// @return the instance
//

- shallowFree
{
  return [super shallowFree];
}

//
// (Deep) free the list (the stored objects are *FREED*)
//
// @return the instance
//

- free
{
  return [super free];
}


//// Member methods

//
// Is the list sorted ascending ?
//
// @return is it ?
//

- (BOOL) ascending
{
  return _ascending;
}

//
// Set the sorting direction 
//
// @param ascending    should the list be sorted ascending ?
// 
// @return the list
//

- (DSortedList *) ascending :(BOOL) ascending
{
  if (ascending != _ascending)
  {
    [self reverse];
  }
  
  return self;
}

//
// Return the class of the objects in the list
// 
// @return the class (or Nil)
// 

- (Class) class
{
  return _class;
}

// 
// Set the class of the objects in the list (only if list is empty)
// 
// @param class        the class for the objects in the list
// 
// @return the object
// 

- (DSortedList *) class :(Class) class
{
  if ([self length] == 0)
  {
    if (class == Nil)
    {
      WARNING(DW_NIL_NOT_ALLOWED, "class");
    }
    else if (![class isClass])
    {
      WARNING(DW_ARG_NOT_CLASS, "class");
    }
    else if (![class conformsTo :@protocol(DComparable)])
    {
      WARNING(DW_PROT_NOT_IMPL, "DComparable");
    }
    else
    {
      _class = class;
    }
  }
  else
  {
    WARNING(DW_UNEXPECTED_ERROR, "list not empty");
  }
  
  return self;
}

//// List manipulation methods

//
// Prepend an object to the list (Not allowed)
//
// @param object   the object that must be prepended
//
// @return the list
//

- (DSortedList *) prepend :(id) object
{
  WARNING(DW_METHOD_NOT_ALLOWED, "prepend:");

  return self;
}

//
// Append an object to the list (Not allowed)
//
// @param object   the object that must be appended
//
// @return the instance
//

- (DSortedList *) append :(id) object
{
  WARNING(DW_METHOD_NOT_ALLOWED, "append:");

  return self;
}

//
// Insert an object in the list on the given index (Not allowed)
//
// @param index    the index in the list (-n..+n)
// @param object   the object to be inserted
//
// @return the list
//

- (DSortedList *) insert :(long) index :(id) object
{
  WARNING(DW_METHOD_NOT_ALLOWED, "insert::");

  return self;
}

//
// Insert an object sorted in the list
// 
// @param object   the object to be inserted
// 
// @return the object
// 

- (DSortedList *) insert :(id) object
{
  if (_class == Nil) 
  {
    WARNING(DW_OBJECT_NOT_INIT, "class");
  }
  else if (object == nil)
  {
    WARNING(DW_INVALID_ARG, "object");
  }
  else if (![object isKindOf :_class])
  {
    WARNING(DW_INVALID_CLASS, "object");
  }
  else
  {
    BOOL inserted = NO;
    
    DListIterator *iter = [DListIterator new];
    
    id walk;
    
    [iter list :self];
  
    walk = [iter last];

    // check if insert sequence is already sorted
    if (_ascending)
    {
      if ((walk == nil) || ([object compare :walk] > 0))
      {
        [iter after :object];
        
        inserted = YES;
      }
    }
    else
    {
      if ((walk == nil) || ([object compare :walk] < 0))
      {
        [iter after :object];
        
        inserted = YES;
      }
    }

    if (!inserted)
    {
      walk = [iter first];
    
      while (walk != nil)
      {
        if (_ascending)
        {
          if ([object compare :walk] < 0)
          {
            [iter before :object];
          
            break;
          }
        }
        else
        {
          if ([object compare :walk] > 0)
          {
            [iter before :object];
          
            break;
          }
        }
        
        walk = [iter next];
      }
    }
  }
  
  return self;
}

//
// Set the object in a list node (Not allowed)
//
// @param index    the index in the list
// @param object   the object to be set
// 
// @return the previous stored object
//

- (id) set :(long) index :(id) object
{
  WARNING(DW_METHOD_NOT_ALLOWED, "set::");

  return self;
}

//
// Reverse the list
//
// @return the list object
//

- (DSortedList *) reverse
{
  [super reverse];
  
  _ascending = !_ascending;

  return self;
}


//// Stackable protocol methods

//
// Push a new node with the object at the end of the list (Not allowed)
//
// @param obj      the object to be pushed
//
// @return success
//
- (BOOL) push :(id) obj
{
  WARNING(DW_METHOD_NOT_ALLOWED, "push:");

  return NO;
}

//// Queuable protocol methods

//
// Enqueue the object at the end of the list (Not allowed)
//
// @param obj      the object 
//
// @return success
//
- (BOOL) enqueue :(id) obj
{
  WARNING(DW_METHOD_NOT_ALLOWED, "enqueue:");

  return NO;
}

//// String methods

//
// Split a string in a list of sorted strings (ascending)
//
// @param string    the string to be splitted
// @param seperator the seperator character
// @param maxsplits the maximum number of splits (or -1 for all)
//
// @return a (new) sorted list with string objects
//

+ (DSortedList *) splitSorted :(const char *) string :(char) seperator :(int) maxsplits
{
  int count = 0;
  int srce  = 0;
  int dest  = 0;
  
  DSortedList *list = [[DSortedList alloc] init];
  
  DText *text;
  
  [list class :[DText class]];
  
  if (seperator != EOS)
  {
    while (string[dest] != EOS)
    {
      srce = dest;
      while ((string[dest+1] != EOS) && ((string[dest+1] != seperator) || ((count >= maxsplits) && (maxsplits != -1))))
      {
        dest++;
      }
  
      text = [DText alloc];
   
      [[text init] set :string :srce :dest];  

      [list insert :text];
      count++;
    
      dest++;
      while (string[dest] == seperator)
        dest++;
    }
  }
  else
    WARNING(DW_INVALID_ARG, "seperator");

  return list;
}

@end

/*===========================================================================*/

